package com.offer;


import com.bean.ListNode;
import com.bean.Node;
import com.bean.TreeNode;
import com.utils.TreeUtils;

import java.util.ArrayList;
import java.util.Currency;
import java.util.List;
import java.util.Stack;

import kotlin.reflect.jvm.internal.impl.utils.DFS;

public class Test36 {

    private Node pre, head;

    public Node treeToDoublyList(Node rootNode) {
        if (rootNode == null) {
            return null;
        }

        dfs(rootNode);
        head.left = pre;
        pre.right = head;

        return head;
    }

    private void dfs(Node cur) {
        if (cur == null) {
            return;
        }

        dfs(cur.left);

        if (pre == null) {
            head = cur;
        } else {
            pre.right = cur;
        }

        cur.left = pre;

        pre = cur;
        dfs(cur.right);
    }


    public static void main(String[] args) {
//        TreeNode rootNode = TreeUtils.buildTree();
//        TreeUtils.showTree(rootNode);

        Node rootNode = new Node(4);
        rootNode.left = new Node(2);
        rootNode.left.left = new Node(1);
        rootNode.right = new Node(5);


        Test36 test34 = new Test36();
        Node result = test34.treeToDoublyList(rootNode);
//        TreeNode result = test34.treeToDoublyList(rootNode);
//        System.out.println("111");
//        TreeUtils.show
    }

}
